package com.skh.binaryTree;

/**
 * @Author: skh
 * @Date: 2020/3/5 14:04
 * @Description: 路径总和 III
 */
public class PathSum {

    /**
     * 给定一个二叉树，它的每个结点都存放着一个整数值。
     *
     * 找出路径和等于给定数值的路径总数。
     *
     * 路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
     *
     * 二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。
     *
     * 示例：
     *
     * root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
     *
     *       10
     *      /  \
     *     5   -3
     *    / \    \
     *   3   2   11
     *  / \   \
     * 3  -2   1
     *
     * 返回 3。和等于 8 的路径有:
     *
     * 1.  5 -> 3
     * 2.  5 -> 2 -> 1
     * 3.  -3 -> 11
     *
     */

    /**
     * 外层递归，提供了每次都是root，里层递归来看从这个root开始有多少个加起来和是等于sum的。
     */
    int count = 0;
    public int pathSum(TreeNode root, int sum) {
        if (root == null) {
            return 0;
        }

        sum(root, sum);
        pathSum(root.left, sum);
        pathSum(root.right, sum);

        return count;
    }

    public void sum (TreeNode node,Integer sum){
        if (node == null) {
            return;
        }

        sum = sum - node.val;
        if (sum == 0) {
            count++;
        }

        sum(node.left, sum);
        sum(node.right, sum);

    }

    public static void test(int sum) {
        if (sum == 0) {
            return;
        }
        System.out.println(sum);
        sum--;
        test(sum);
        test(sum);
    }

    public static void main(String[] args) {
        PathSum.test(3);

    }
}
